Longest mountain in array [Two Pointers]

Time: O(N); Space: O(1); medium

Let’s call any (contiguous) subarray B (of A) a mountain if the following properties hold: B.length >= 3 There exists some 0 < i < B.length - 1 such that B[0] < B[1] < … B[i-1] < B[i] > B[i+1] > … > B[B.length - 1] (Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain. Return 0 if there is no mountain.

Example 1:

Input: A = [2, 1, 4, 7, 3, 2, 5]

Output: 5

Explanation:

  • The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: A = [2, 2, 2]

Output: 0

Explanation:

  • There is no mountain.

Notes:

  • 0 <= A.length <= 10000

  • 0 <= A[i] <= 10000

Follow up:

Can you solve it using only one pass? Can you solve it in O(1) space?

Intuition Without loss of generality, a mountain can only start after the previous one ends. This is because if it starts before the peak, it will be smaller than a mountain starting previous; and it is impossible to start after the peak.

Algorithm For a starting index base, let’s calculate the length of the longest mountain A[base], A[base+1], …, A[end]. If such a mountain existed, the next possible mountain will start at base = end; if it didn’t, then either we reached the end, or we have A[base] > A[base+1] and we can start at base + 1.

Example

Here is a worked example on the array A = [1, 2, 3, 2, 1, 0, 2, 3, 1]: Worked example of A = [1,2,3,2,1,0,2,3,1]

base starts at 0, and end travels using the first while loop to end = 2 (A[end] = 3), the potential peak of this mountain. After, it travels to end = 5 (A[end] = 0) during the second while loop, and a candidate answer of 6 (base = 0, end = 5) is recorded.

Afterwards, base is set to 5 and the process starts over again, with end = 7 the peak of the mountain, and end = 8 the right boundary, and the candidate answer of 4 (base = 5, end = 8) being recorded.

[1]:

class Solution1(object):
    def longestMountain(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        N = len(A)
        result = base = 0

        while base < N:
            end = base
            if end + 1 < N and A[end] < A[end + 1]: #if base is a left-boundary
                #set end to the peak of this potential mountain
                while end+1 < N and A[end] < A[end+1]:
                    end += 1

                if end + 1 < N and A[end] > A[end + 1]: # if end is really a peak..
                    # set 'end' to right-boundary of mountain
                    while end + 1 < N and A[end] > A[end + 1]:
                        end += 1
                    # record candidate answer
                    result = max(result, end - base + 1)

            base = max(end, base + 1)

        return result

[2]:

s = Solution1()
A = [2, 1, 4, 7, 3, 2, 5]
assert s.longestMountain(A) ==  5
A = [2, 2, 2]
assert s.longestMountain(A) ==  0

[3]:

class Solution2(object):
    def longestMountain(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        result, up_len, down_len = 0, 0, 0

        for i in range(1, len(A)):
            if (down_len and A[i-1] < A[i]) or A[i-1] == A[i]:
                up_len, down_len = 0, 0
            up_len += A[i-1] < A[i]
            down_len += A[i-1] > A[i]
            if up_len and down_len:
                result = max(result, up_len + down_len + 1)

        return result

[4]:

s = Solution2()
A = [2, 1, 4, 7, 3, 2, 5]
assert s.longestMountain(A) ==  5
A = [2, 2, 2]
assert s.longestMountain(A) ==  0